from cmath import inf
from typing import List


class Solution:
    def numberOfSets(self, n: int, maxDistance: int, roads: List[List[int]]) -> int:
        # 初始化邻接矩阵 g，初始值为无穷大，表示节点之间的距离
        g = [[inf] * n for _ in range(n)]
        # 遍历所有的道路，更新邻接矩阵 g 中的距离值
        for x, y, wt in roads:
            g[x][y] = min(g[x][y], wt)
            g[y][x] = min(g[y][x], wt)

        # 初始化一个长度为 n 的列表 f，用于存储中间结果
        f = [None] * n

        # 定义一个内部函数 check，用于检查给定节点集合 s 是否满足条件
        def check(s: int) -> int:
            # 遍历所有节点，将在集合 s 中的节点的邻接矩阵行复制到 f 中
            for i, row in enumerate(g):
                if s >> i & 1:  # i 在集合 s 中
                    f[i] = row.copy()

            # Floyd 算法（只考虑在 s 中的节点）
            # 通过中间节点 k 来更新节点 i 和 j 之间的最短路径
            for k in range(n):
                # 节点k 不在 s中 跳过
                if (s >> k & 1) == 0:  # k 不在集合 s 中，表示当前节点不在集合中
                    continue
                for i in range(n):
                    # 节点 i 不在s中 跳过
                    if (s >> i & 1) == 0 or f[i][k] == inf:  # 不存在f[i][k]这条边
                        continue
                    for j in range(n):
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j])

            # 判断保留的节点之间的最短路是否均不超过 maxDistance
            for i, di in enumerate(f):
                if (s >> i & 1) == 0:  # i 不在集合 s 中
                    continue
                for j, dij in enumerate(di[:i]):
                    if s >> j & 1 and dij > maxDistance:
                        return 0
            return 1

        # 枚举所有可能的节点子集 s，作为保留的节点，判断这些节点是否满足要求
        # 对满足要求的子集数量进行求和并返回
        return sum(check(s) for s in range(1 << n))